﻿/*
 *  Created on: 28.01.2012
 *  Author: Pocmukc
 *  mailto: pocmukc@alt.ru
 *  
 * ===============  Задача ===================== 
 * найти поднабор A из набора B, чтобы сумма его
 * элеметов не привышила заданного числа
 * =============================================
 * 
 * Класс Calculator:
 *  wts - Массив элементов для упаковки
 *  
 *  Поля:
 *  maxLength - максимальный размер контейнера
 *  Count - количество контейнеров
 *  
 *  Methods
 *  -constructor(wts, length) - принимаест набор чисел wts для упаковки в котейнеры с размером length
 *  -getFreeSpaces() - возращает List<int> свободного места незаполненных контейнеров
 *  -getMaxSize(), getMinSize(), getAverageSize() возращают строку
 *      содержащую процентное соотношение свободного пространства
 *      (максимально/минимально/средне заполненного контейнера из незаполненных)
 *      к максимальному размеру контейнера
 *      пример 67,23% 
 *      *** - в среднем значении берется количество незаполненных контейнеров(а не общее)
 *  -toString() - возвращает строку вида
 *      №{порядковый номер контейнера}: {содержимое контенера}: {свободное место в контейнере} \n
 *      Количество строк = кол-ву контейнеров
 *      
 * ======
         *  (!!!исключен)-getContainers() - взращает набор элементов List <containers>
         *  |   Ошибка: Несовместимость по доступности: доступность возвращаемого типа 
         *  |   "System.Collections.Generic.List<calculator.Calculator.container>" 
         *  |   ниже доступности метода "calculator.Calculator.getContainers()"
 * ======
 */

using System;
using System.Collections.Generic;

namespace calculator
{
    class Calculator
    {

        // открытые методы
        public Calculator(List<int> wts, int maxLength)
        {
            this.wts = new List<int>();
            foreach (int i in wts)
                if (i <= maxLength && i > 0)
                    this.wts.Add(i);
            this.maxLength = maxLength;
            calc();
        }



        private void calc()
        {
            wts.Sort(compare);
            containers = new List<container>();
            containers.Add(new container(maxLength));
            foreach (int i in wts)
            {
                int index = findMinAmount(i);
                if (containers[index].freeAmount - i >= 0)
                {
                    containers[index].freeAmount -= i;
                    containers[index].addElem(i);
                }
                else
                {
                    container newContainer = new container(maxLength - i);
                    newContainer.addElem(i);
                    containers.Add(newContainer);
                }
            }
            Count = containers.Count;
        }
        /*
                public List<container> getContainers()
                {
                    return containers;
                }
        */
        public int Count;

        public List<int> wts;

        public int maxLength;

        public List<int> getFreeSpaces()
        {
            List<int> res = new List<int>();
            foreach (container cnt in containers)
                if (cnt.freeAmount > 0)
                    res.Add(cnt.freeAmount);
            res.Sort();
            return res;
        }

        public string getMinSize()
        {
            int min = 0xFFFFFFF;
            List<int> spaces = getFreeSpaces();
            foreach (int i in spaces)
                if (i < min && i > 0)
                    min = i;
            double res = (double)min * 100 / maxLength;
            return res.ToString("F") + "%";
        }

        public string getMaxSize()
        {
            int max = 0;
            List<int> spaces = getFreeSpaces();
            foreach (int i in spaces)
                if (i > max)
                    max = i;
            double res = (double)max * 100 / maxLength;
            return res.ToString("F") + "%";
        }

        public string getAverageSize()
        {
            int sum = 0;
            List<int> spaces = getFreeSpaces();
            foreach (int i in spaces)
                if (i > 0)
                    sum += i;
            double res = (double)sum * 100 / (maxLength * spaces.Count);
            return res.ToString("F") + "%";
        }

        public string toString()
        {
            string str = "";
            for (int i = 0; i != containers.Count; ++i)
                str += "№" + (i + 1).ToString() + ": " + containers[i].toString()
                    + ": " + containers[i].freeAmount + "\r\n";
            return str;
        }

        // закрытые методы и поля

        /* Класс container
         * freeAmount - свободное место в контейнере
         * size() - выдает количество содержащихся елементов
         * toString(!!!to пишется с маленькой буквы) выдает елементы 
         *      в одну строку(без параметра freeAmount)
         * summary - выдает сумму листа элементов
         */
        private class container
        {
            // открытые поля и методы
            public int freeAmount;
            public container(int containerSize)
            {
                freeAmount = containerSize;
                elems = new List<int>();
            }

            public string toString()
            {
                string outbuffer = "";
                foreach (int i in elems)
                    outbuffer += i.ToString() + " ";
                return outbuffer;
            }

            public int summary()
            {
                int sum = 0;
                foreach (int i in elems)
                    sum += i;
                return sum;
            }

            public int size()
            {
                return elems.Count;
            }

            public void addElem(int num)
            {
                elems.Add(num);
            }

            // закрытое поле
            private List<int> elems;
        }

        private List<container> containers;

        /*
         * Поиск наиболее подходящего контейнера
         * Находит индекс контейнера с минимальным
         * свободным местом для размещения отрезка 
         * данной длины; если размер места совпадает
         * с размером отрезка, то возращается индекс
         * этого контейнера.
         */

        private int findMinAmount(int length)
        {
            int k = 0; int minLength = 0xFFFFFFF;
            for (int i = 0; i != containers.Count; ++i)
            {
                int place = containers[i].freeAmount - length;
                if (place != 0)
                {
                    if (place > 0 && place < minLength)
                    {
                        minLength = place;
                        k = i;
                    }
                }
                else
                    return i;
            }
            return k;
        }

        /*
         * Callback функция для сортировки чисел
         * в обратном порядке
         * возвращает:
         * return < 0 : x > y
         * return = 0 : x = y
         * return > 0 : x < y
         */

        private static int compare(int x, int y)
        {
            return y - x;
        }
    }
}
